package com.ztl.leetcode.SwordFingerOffer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author @ztl
 * @ClassName:CopyLinkedList
 * @Package:com.ztl.leetcode.SwordFingerOffer
 * @date 2023年05月14日 20:28
 * @description: 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中;
 * 每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 * @version: 1.0
 */
public class CopyLinkedList_35 {
    //遍历两次链表，时间复杂度O(n),使用Map存储链表，空间复杂度O(n)
    public Node copyRandomList(Node head) {
        //思路：使用HashMap的存储特点，将原Node作为key，复制后的Node作为value存入Map中
        //此时的原Node存储位置与新Node存储位置一致
        //那么，原Node的random属性存储位置 = 新Node的random属性存储位置
        //只需将每个原Node的random存放在Map中的位置获取到，使新Node的random值指向对应位置的新Node节点即可

        //非空判断
        if(head == null) return null;

        //使用临时接节点，避免破坏原节点
        Node cur = head;

        //使用HashMap的键值对存放原节点和新节点
        Map<Node, Node> map = new HashMap<>();

        //开始循环创建新节点
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        //创建完成，此时新节点并只有值，并没有形成链表

        //重置零时节点指向
        cur = head;

        //第二轮循环为新节点建立链接关系
        while(cur != null) {
            //'='号左边：新节点.next
            //'='号右边：新节点.next位置
            //使用原节点key获取对应的next和random所在Map中的位置,把该位置的value与新节点建立关系
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //最后返回新链表
        return map.get(head);
    }
}
